Problem statement: zenit16ckj

Jankova brigáda

Počet bodov: 16, časový limit: 1000ms

Janko je veľmi usilovný. Už počas školy si neodpustí len tak nič nerobiť a tak si privyrába roznášaním letákov. Bola mu zverená nejaká obytná časť, v ktorej má roznosiť letáky. Táto časť je súvislá, t.j. z každej jemu zverenej ulice sa dá len pomocou jeho ulíc a križovatiek medzi nimi dostať postupne na ľubovoľnú inú jeho ulicu.

Nerád ale robí zbytočné veci a teda by nerád po nejakej ulici išiel viac ako raz. Pri prvom prechode totiž už všetky letáky roznesie a druhýkrát by to už bolo dosť zbytočné. Zároveň však aspoň raz po každej ulici prejsť musí, ináč za svoju lajdácku prácu nič nedostane.

Úloha

Pre danú obytnú časť by Janka zaujímalo, či vie rozniesť letáky tak, že začína na križovatke \(v\), prejde každou ulicou práve raz a vráti sa na križovatku \(v\).

Vstup a výstup

Na prvom riadku vstupu dostanete postupne prirodzené čísla \(n, m, v\) reprezentujúce počet križovatiek (\(2 \leq n \leq 100\,000\)), počet ulíc (\(1 \leq m \leq 100\,000\)) a začiatočnú (teda aj konečnú) križovatku (\(1 \leq v \leq n\)).

Nasleduje \(m\) riadkov, každý z nich opisujúci jednu ulicu. Ulica je daná dvojicou križovatiek \(a, b\), ktoré spája (\(1 \leq a,b \leq n\)). Môžete predpokladať, že žiadna ulica nebude na vstupe viac ako raz.

Takisto môžete predpokladať, že na vstupe nebudú žiadne zbytočné križovatky, t.j. pre všetky čísla od \(1\) po \(n\) platí, že sa aspoň v jednej ulici táto križovatka spomína.

Na jediný riadok výstupu vypíšte ide, ak sa dá z križovatky \(v\) prejsť každou ulicou práve raz a vrátiť sa. V opačnom prípade vypíšte nejde. Nezabudnite na znak konca riadku.

 Príklad

Input:

3 3 3
1 2
2 3
3 1

Output:

ide

Input:

4 3 3
1 3
4 2
3 4

Output:

nejde